package codetop.microsoft.T347;

import java.util.*;

/**
 * @Author: 18362
 * @Create: 2022-08-16 9:06:46 星期二
 */
class Solution {
    // 最小堆或桶排序法，最小堆是O(nlogk)，桶排序是O(n)，两者的空间复杂度都是O(n)
    public int[] topKFrequent(int[] nums, int k) {
        int[] res = new int[k];
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<Integer>[] bucket = new List[nums.length+1];
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (bucket[entry.getValue()] == null)
                bucket[entry.getValue()] = new ArrayList<>();
            bucket[entry.getValue()].add(entry.getKey());
        }
        int cnt = 0;
        for (int i=bucket.length-1; i>=0 && cnt < k; --i) {
            if (bucket[i] != null) {
                for (int j=0; j<bucket[i].size(); ++j)
                    res[cnt++] = bucket[i].get(j);
            }
        }
        return res;
    }
}